﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <set>

using namespace std;


//给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
//
//不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//
//元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
class Solution
{
public:
    int removeElement(vector<int>& nums, int val)
    {
        int left = 0, right = 0, n = nums.size();
        // 双指针算法
        while (right < n)
        {
            if (nums[right] == val)
            {
                right++;
            }
            else
            {
                swap(nums[left++], nums[right++]);
            }
        }

        return left;
    }
};

class Solution
{
public:
    // 1. 设置一个变量count，用来记录nums中值等于val的元素的个数
    // 2. 遍历nums数组，对于每个元素进行如下操作：
    // a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
    // b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
    // 因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
    // 因此次数需要将nums[i]往前搬移
    // 3. 返回删除之后新数组中有效元素个数
    int removeElement(vector<int>& nums, int val)
    {
        int count = 0, n = nums.size();
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == val)count++;
            else nums[i - count] = nums[i];
        }

        return n - count;
    }
};

//恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。
//我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
//骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
//若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），
//要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
//为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon)
    {
        // dp[i][j]表示从i,j位置出发到终点需要的最低生命值
        // 向下走
        // x + dungeon[i][j] >= dp[i+1][j]
        // x >= dp[j+1][j] - dungeon[i][j]
        // 向右走
        // x + dungeon[i][j] >= dp[i][j+1]
        // x >= dp[i][j+1]-dungeon[i][j]
        // 取向下走和向右走的最小值
        // 当最小值小于0的时候，我们需要将其设置为1
        // 注意越界的问题--需要在最下面加一行和最右边加一行
        // 最后一个位置的值为1，那么需要将其右边和下边的值设置为1，
        // 其余的设置为最大整形即可
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                // 保证在该位置活着
                /*如果当前位置的 dungeon[i][j] 是⼀个⽐较⼤的正数的话， dp[i][j] 的值可能变
                    成 0 或者负数。也就是最低点数会⼩于 1 ，那么骑⼠就会死亡。因此我们求出来的 dp[i][j] 如果⼩于等于 0 的话，
                    说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i] [j] 与 1 取⼀个最⼤值即可：
                    dp[i][j] = max(1, dp[i][j])*/
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        return dp[0][0];
    }
};

//一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
//在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
//给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
class Solution
{
public:
    int massage(vector<int>& nums)
    {
        // dp[i]表示选择到i位置的时候,此时的最大预约时长
        // f[i]表示选择nums[i]时的最大预约时长
        // f[i] = g[i-1] + nums[i];
        // g[i]表示不选择nums[i]时的最大预约时长
        // 那么i-1位置可能选了，可能没有选
        // i-1位置选了: g[i] = f[i-1]
        // i-1位置没有选: g[i] = g[i-1]
        // g[i] = max(f[i-1],g[i-1]);
        int n = nums.size();
        vector<int> f(n);
        // 处理边界情况
        if (n == 0) return 0;
        vector<int> g(n);
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};

//给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，
//返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

// 利用set数据结构
class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        set<int> st;
        for (auto x : nums)
            st.insert(x);
        int i = 0;
        for (auto x : st)
        {
            nums[i] = x;
            i++;
        }

        return i;
    }
};

// 双指针算法
class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;
        // 第一个元素一定可以保留
        int left = 1, right = 1;
        while (right < n)
        {
            // 说明right之前的元素都不同,直接赋值给left
            if (nums[right] == nums[right - 1]) right++;
            else nums[left++] = nums[right++];
        }

        return left;
    }
};
int main()
{
	return 0;
}